package cn.edu.jxau.test;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author 付大石
 */
public class Sort {

    public static void main(String[] args) throws IOException {

//        int len = 10000;
//        int[] arr = new int[len];
//        DataInputStream in = new DataInputStream(new FileInputStream("C:\\Users\\PC-Clive\\Desktop\\data.dat"));
//        for (int i = 0; i < arr.length; i++) {
//            arr[i] = in.readInt();
//        }
//        in.close();

        int[] arr = {2,3,5,7,3,6,8,2,6,9,5,7,4,3,6,8,9,4,7,4,8,3,8,3};
        System.out.println(Arrays.toString(arr));
        long start = System.nanoTime();
        sort(arr);
        long end = System.nanoTime();
        System.out.println(Arrays.toString(arr));
        System.out.println("spend tiem:" + (end - start));

    }

    /**
     * 桶排序
     * 
     * @param arr
     */
    private static void sort(int[] arr) {
        
        List<Integer>[] bucketList = new ArrayList[10]; //接受键值范围是[0,9]
        for(int i=0;i<arr.length;i++) {
            if(bucketList[arr[i]] == null) {
                bucketList[arr[i]] = new ArrayList<Integer>();
            }
            bucketList[arr[i]].add(arr[i]);
        }
        int k = 0;
        for(int i=0;i<bucketList.length;i++) {
            List<Integer> list = bucketList[i];
            if(list != null) {
                for(Integer item : list) {
                    arr[k++] = item;
                }
            }
        }
    }
}
